package algorithm.swordoff;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 和为s的连续正数序列
 *
 * 回溯, 组合+剪枝
 */

public class SQ57_2 {
    public int[][] findContinuousSequence(int target) {
        int[] candidates = new int[target - 1];
        for (int i = 0; i < target - 1; i++) candidates[i] = i + 1;
        List<List<Integer>> ansList = new LinkedList<>();

        // 尝试每个起始的位置,优化到candidates.length/2
        for (int i = 0; i < candidates.length / 2; i++) backTrack(ansList, new ArrayList<>(), candidates, target, i);

        // 下面这些是为了配合返回类型多写的睿智代码
        int[][] ans = new int[ansList.size()][];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = ansList.get(i).stream().mapToInt(Integer::intValue).toArray();
        }
        return ans;
    }

    public List<List<Integer>> listReturnType(int target) {
        int[] candidates = new int[target - 1];
        for (int i = 0; i < target - 1; i++) candidates[i] = i + 1;
        List<List<Integer>> ansList = new LinkedList<>();
        for (int i = 0; i < candidates.length / 2; i++) {
            backTrack(ansList, new ArrayList<>(), candidates, target, i);
        }
        return ansList;
    }

    private void backTrack(List<List<Integer>> totalAns,
                           List<Integer> curr,
                           int[] candidates,
                           int target,
                           int searchFromWhere) {
        if (target <= 0) {
            if (target == 0) totalAns.add(new ArrayList<>(curr));
            return;
        }

        curr.add(candidates[searchFromWhere]);
        backTrack(totalAns, curr, candidates, target - candidates[searchFromWhere], searchFromWhere + 1);
        curr.remove(curr.size() - 1);

    }

    // 双指针法,快就完事
    // 注意左指针和右指针必定都向右移动
    // 一个左指针必定至多只有一个右指针与其匹配,并且当左指针递增的时候,右指针也必定递增(不可能不动或者向左)
    public int[][] findContinuousSequence2(int target) {
        int i = 1, j = 2, s = 3;
        List<int[]> res = new ArrayList<>();
        while (i < j) {
            if (s == target) {
                int[] ans = new int[j - i + 1];
                for (int k = i; k <= j; k++)
                    ans[k - i] = k;
                res.add(ans);
            }
            if (s >= target) {
                s -= i;
                i++;
            } else {
                j++;
                s += j;
            }
        }
        return res.toArray(new int[0][]);
    }

    /**
     *
     * @param target
     * @return
     */
    public int[][] findContinuousSequence3(int target) {
        List<int[]> ans = new LinkedList<>();

        int left = 1, right = 2, sum = 3;
        // 细节一:为什么left == right就结束了,单个数字都等于target了,后面的数字肯定加和都大于target了
        while (left < right) {
            if (sum == target) ans.add(continuousArray(left, right-left+1));
            // 细节二:如果等于target之后,下面的还是要执行,左指针(主指针)继续向后移动
            if (sum < target) { right++; sum += right; }
            // 细节三:左指针移动的时候sum是先减再移动指针,而右指针动的时候是指针先动再动sum
            else { sum -= left; left++; }
        }
        return ans.toArray(new int[0][]);
    }

    public int[] continuousArray(int begin, int length) {
        int[] ans = new int[length];
        for (int i = 0; i < length; i++) ans[i] = begin+i;
        return ans;
    }


    public static void main(String[] args) {
        SQ57_2 sq57_2 = new SQ57_2();
        int[][] ccc = sq57_2.findContinuousSequence3(9);
        for (int[] ints : ccc) {
            System.out.println(Arrays.toString(ints));
        }
    }

}
